/**
 * FileName: RandomizedBST.c
 * -------------------------------------------------------------
 * - 随机插入
 * - 随机删除
 * - 随机合并
 */
#include <stdlib.h>

//见Item.h
typedef struct Item* Item;
typedef char Key;
typedef int Value;
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

struct Item {
    Key key;
    Value value;
};

typedef struct STnode* link;

struct STnode {
    Item item;
    link l;
    link r;
    int N;
};

link head;
link z;

/***********************************函数声明*******************************/
int size(link);
void update_N(link h);
link NEW(Item, link, link, int);
link rotL(link);
link rotR(link);
link partR(link, int);
link insertR(link, Item);
link insertT(link, Item);
link insertR2(link, Item);
Item searchR(link, Key);
void sortR(link, void (*visit)(Item));
link deleteR(link, Key);
link joinLR(link, link);
link joinLR2(link, link);
link joinR(link, link);


void STinit();
int STcount();
void STinsert(Item);
Item STsearch(Key);
void STsort(void (*visit)(Item));
Item STselect(int);
void STdelete(Key);
link STjoin(link, link);

/***********************************辅助函数部分*******************************/
link NEW(Item item, link l, link r, int N) {
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    x->N = N;
    return x;
}

Item searchR(link h, Key v) {
    if (h == z) {
        return NULLitem;
    }
    Key t = key(h->item);
    if (eq(v, t)) {
        return h->item;
    }
    if (less(v, t)) {
        return searchR(h->l, v);
    }else {
        return searchR(h->r, v);
    }
}

void sortR(link h, void (*visit)(Item)) {
    if (h == z) {
        return;
    }
    sortR(h->l, visit);
    visit(h->item);
    sortR(h->r, visit);
}

int size(link h) {
    if (h == z) {
        return 0;
    }else {
        return h->N;
    }
}

void update_N(link h) {
    if (h != z) {
        h->N = size(h->l)+size(h->r)+1;
    }
}

/**
 * Program 13.4 Deletion in a randomized BST
 *----------------------------------------------------------------------------------------------
 * We use the same `STdelete` function as we did for standard BSTs (see Program 12.15),
 * but replace the `joinLR` function with the one shown here,
 * which makes a randomized, rather than an arbitrary, decision about whether to
 * replace the deleted node with the predecessor or the successor,
 * using probabilities that ensure that each node in the resulting tree is equally likely to be the root.
 * To properly maintain the node counts, we also need to include a call to `fixN` (see Program 13.3)
 * for `h` before returning from `removeR`.
 */
link joinLR2(link a, link b) {
    if (b == z) {
        return a;
    }
    if (a == z) {
        return b;
    }
    if (rand()/RAND_MAX < a->N/(a->N+b->N)) {
        a->r = joinLR2(a->r, b);
        return a;
    }else {
        b->l = joinLR2(a, b->l);
        return b;
    }
}

/**
 * Program 12.15 Deletion of a node with a given key in a BST
 * -----------------------------------------------------------------------------------------------------
 * This implementation of the `delete` operation removes the first node with key `v` encountered in the BST.
 *
 * Working top down, it makes recursive calls for the appropriate subtree until the node to be deleted is at the root.
 * Then, it replaces the node with the result of combining its two subtrees
 * — the smallest node in the right subtree becomes the root, then its left link is set to point to the left subtree.
 */

// link joinLR(link a, link b) {
//     if (b == z) {
//         return a;
//     }
//     b = partR(b, 0);
//     b->l = a;
//     return b;
// }

link deleteR(link h, Key v) {
    // 基本情况：如果当前节点是哨兵节点（空树），说明要删除的键不存在于此路径，直接返回哨兵。
    if (h == z) {
        return z;
    }

    link x; // 临时指针，用于保存待删除节点，以便后续释放内存
    Key t = key(h->item); // 获取当前节点的键

    // 递归查找待删除节点：
    // 如果要删除的键v小于当前节点的键t，则在左子树中递归查找并删除
    if (less(v, t)) {
        h->l = deleteR(h->l, v);
    }
    // 如果要删除的键v大于当前节点的键t，则在右子树中递归查找并删除
    else if (less(t, v)) { // 注意这里使用 else if，确保只有一种情况被执行
        h->r = deleteR(h->r, v);
    }
    // 找到了待删除节点：当前节点h的键t等于要删除的键v
    else { // if (eq(v, t))
        x = h; // 记录当前节点h，准备删除

        // **关键步骤：合并左右子树**
        // 调用 joinLR 函数合并h的左子树(h->l)和右子树(h->r)。
        // joinLR 会将右子树中最小的元素（即h的中序后继）提升为合并后的新根，
        // 并将h的左子树连接到新根的左侧。
        // 合并后的结果将替换掉当前节点h。
        h = joinLR2(h->l, h->r);
        free(x); // 释放原删除节点的内存
    }

    // **重要：更新节点计数**
    // 无论是否发生了删除或结构改变，当前路径上的节点数量都可能受影响（尤其是在递归返回时），
    // 确保 h->N 字段反映其子树的最新大小。
    // 注意：这里的 update_N(h) 放置位置很重要，确保在所有子树操作完成后才更新当前节点。
    update_N(h);
    return h; // 返回更新后的子树根
}

/**
 * Program 12.11 Rotations in BSTs
 * ---------------------------------------------------------------------------------------------------------
 * These twin routines perform the rotation operation on a BST.
 * A right rotation makes the old root the right subtree of the new root (the old left subtree of the root).
 * A left rotation makes the old root the left subtree of the new root (the old right subtree of the root).
 *
 * For implementations where a count field is maintained in the nodes
 * (for example, to support `select`, as we will see in Section 14.9),
 * we need also to exchange the `count` fields in the nodes involved in the rotation (see Exercise 12.72).
 * ---------------------------------------------------------------------------------------------------------
 * 右旋
 * @param h
 * @return
 * ---------------------------------------------------------------------------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的左孩子
 *
 * 显然有：h的键大于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->l;
 * - 新根的右孩子节点x->r;
 *
 * 右旋的本质是将旧根的左链接逆向
 */
link rotR(link h) {
    link x = h->l;
    h->l = x->r;
    x->r = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * 左旋
 * @param h
 * @return
 * -----------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的右孩子
 *
 * 显然有：h的键小于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->r;
 * - 新根的左孩子节点x->r;
 *
 * 左旋的本质是将旧根的右链接逆向
 */
link rotL(link h) {
    link x = h->r;
    h->r = x->l;
    x->l = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * Program 12.12 Root insertion in BSTs
 * ----------------------------------------------------------------------------------
 * With the rotation functions in Program 12.11,
 * a recursive function that inserts a new node at the root of a BST is immediate:
 * - Insert the new item at the root in the appropriate subtree,
 * - then perform the appropriate rotation to bring it to the root of the main tree.
 * ----------------------------------------------------------------------------------
 * 在根部插入递归版
 * @param h 主树的根
 * @param v 待插入项
 * @return
 */
link insertT(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    if (less(v, key(h->item))) {
        h->l = insertT(h->l, item);
        h = rotR(h);
    }else {
        h->r = insertT(h->r, item);
        h = rotL(h);
    }
    return h;
}

/**
 * 在底部插入项
 * @param h
 * @param item
 * @return
 * -------------------------------------------
 * insertT是insertR的自适应版本
 *
 */
link insertR(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR(h->l, item);
    }else {
        h->r = insertR(h->r, item);
    }
    update_N(h);
    return h;
}

/**
 * Program 13.2 Randomized BST insertion (递归版)
 * -----------------------------------------------------------------------------------
 * 在向一棵包含 N 个节点的 BST 中插入新项时，
 * 我们希望“以概率 1/(N+1) 将新节点插入到根部”，
 * 否则按普通 BST 插入规则递归下去。
 *
 * 概率推导：
 *   令 U = rand() / RAND_MAX ∈ [0,1)，
 *   则事件 U < 1/(N+1) 发生的概率恰好为 1/(N+1)。
 *
 * 实现技巧：
 *   为避免浮点运算，也可以写成
 *     rand() < RAND_MAX/ (N + 1)
 *   此时两边均为整数比较，等价于上面的浮点判断。
 * ------------------------------------------------------------------------------------
 * 参数：
 * @param h    - 当前子树根节点指针（z 表示空树哨兵）。
 * @param item - 待插入的记录。
 *
 * @return     - 插入新节点后的子树根指针。
 */
link insertR2(link h, Item item) {
    // 空树——直接创建新节点，子树规模为 1
    if (h == z) {
        return NEW(item, z, z, 1);
    }

    // 以 1/(h->N + 1) 的概率，使用“根插入”策略
    // 等价于：((double)rand() / RAND_MAX < 1.0 / (h->N + 1)
    if (rand() < RAND_MAX/(h->N + 1)) {
        // 根部插入
        return insertT(h, item);
    }

    // 否则，底部插入
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR2(h->l, item);
    } else {
        h->r = insertR2(h->r, item);
    }

    // 更新当前子树节点计数
    update_N(h);
    return h;
}

/**
 * Program 12.13 Selection with a BST
 * ------------------------------------------------------------------------------------------------------
 * The recursive function `selectR` finds the item with the kth smallest key in a BST.
 * It uses zero-based indexing—for example, we take k = 0 to look for the item with the smallest key.
 * This code assumes that each tree node has its subtree size in the `N` field.
 * - Compare the program with quicksort-based selection in an array (Program 9.6).
 * ------------------------------------------------------------------------------------------------------
 * 从根h处查找第k小的项
 * @param h
 * @param k
 * @return
 * ------------------------------------------------------------------------------------------------------
 * 思路：
 * 检查h的左孩子的节点数t。
 * - 如果t>k，则表示第k小的项在左子树中，递归在左子树中查找第k小的项
 * - 如果t<k，则表示第k小的项在右子树中，递归在右子树中查找第k-t-1小的项
 * - 否则，说明当前节点h的左子树中有k个元素，h是第k+1大的元素，满足条件直接返回
 */
Item selectR(link h, int k) {
    if (h == z) {
        return NULLitem;
    }

    int t = h->l == z ? 0 : size(h->l);
    if (t < k) {
        return selectR(h->r, k - t - 1);
    }
    if (t > k) {
        return selectR(h->l, k);
    }
    return h->item;
}

/**
 * BST的划分操作：将子树中键值第k小的元素移动到根部
 * @param h 当前子树的根节点
 * @param k 目标元素在当前子树中的零基索引（例如 k=0 表示最小元素）
 * @return 经过划分后，以键值第k小的元素为根的新子树的根节点
 * ---------------------------------------------------------------------------------------------------
 * Program 12.14 Partitioning of a BST
 * ---------------------------------------------------------------------------------------------------
 * 思路：
 * partR是selectR的自适应版本，思想是将最近（或当前）操作的元素（即第k小的元素）提升到根部。
 * 这样做能够将树以该元素为“枢轴”进行划分，使得小于它的元素都在左子树，大于它的元素都在右子树。
 *
 */
link partR(link h, int k) {
    if (h == z) {
        return NULLitem;
    }
    int t = h->l == z ? 0 : size(h->l);
    if (t < k) {
        h->r = partR(h->r, k - t - 1);
        h = rotL(h);
    }
    if (t > k) {
        h->l = partR(h->l, k);
        h = rotR(h);
    }
    return h;
}

link joinR(link a, link b) {
    if (a == z) {
        return b;
    }
    b = insertR2(b, a->item);
    b->l = STjoin(a->l, b->l);
    b->r = STjoin(a->r, b->r);
    update_N(b);
    free(a);
    return b;
}

/***********************************接口部分*******************************/
void STinit() {
    z = NEW(NULLitem, 0, 0, 0);
    head = z;
}

int STcount() {
    return head->N;
}

/**
 * STinsert
 * @param item
 * 思路：
 * - 随机选择在底部和根部插入
 */
void STinsert(Item item) {
    // 插入(随机版本)
    head = insertR2(head, item);
}

Item STsearch(Key v) {
    return searchR(head, v);
}

void STsort(void (*visit)(Item)) {
    sortR(head, visit);
}

/**
 * 寻找第k小的项
 * @param k
 * @return
 * ------------------------------------------------------------------------------------------------------
 * 思路：
 * - 标准版本
 * - 自适应版本
 */
Item STselect(int k) {
    //普通版本
    return selectR(head, k);
    // // 自适应版本
    // head = partR(head, k);
    // return head->item;
}

void STdelete(Key v) {
    head = deleteR(head, v);
}

/**
 * Program 12.16 Joining of two BSTs
 * --------------------------------------------------------------------------------------------
 * If either BST is empty, the other is the result.
 * Otherwise,
 * - we combine the two BSTs by (arbitrarily) choosing the root of the first as the root,
 * root inserting that root into the second,
 * - then (recursively) combining the pair of left subtrees and the pair of right subtrees.
 * --------------------------------------------------------------------------------------------
 * @param a
 * @param b
 * @return
 */
// link STjoin(link a, link b) {
//     if (b == z) {
//         return a;
//     }
//     if (a == z) {
//         return b;
//     }
//     b = insertT(b, a->item);
//     b->l = STjoin(a->l, b->l);
//     b->r = STjoin(a->r, b->r);
//     free(a);
//     update_N(b);
//     return b;
// }

/**
 * Program 13.3 Randomized BST combination
 * ------------------------------------------------------------------------------------
 * This function uses the same method as Program 12.16, except that it makes a randomized,
 * rather than an arbitrary, decision about which node to use for the root in a combined tree,
 * using probabilities that ensure that each node is equally likely to be the root.
 *
 * The function `fixN` updates `b->N` to be 1 plus the sum of the corresponding fields
 * in the subtrees (0 for null trees).
 */
link STjoin(link a, link b) {
    if (rand()/RAND_MAX < a->N/(a->N + b->N)) {
        return joinR(a, b);
    }else {
        return joinR(b, a);
    }
}

